
/**
 * An ugly number is a positive integer whose prime factors are limited to 2, 3,
 * and 5.
 * <p>
 * Given an integer n, return the nᵗʰ ugly number.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input: n = 10
 * Output: 12
 * Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10
 * ugly numbers.
 * <p>
 * <p>
 * Example 2:
 * <p>
 * <p>
 * Input: n = 1
 * Output: 1
 * Explanation: 1 has no prime factors, therefore all of its prime factors are
 * limited to 2, 3, and 5.
 * <p>
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= n <= 1690
 * <p>
 * <p>
 * Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 1004 👎 0
 */


package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00264UglyNumberIi {
    public static void main(String[] args) {

        Solution solution = new ID00264UglyNumberIi().new Solution();
        solution.nthUglyNumber(10);
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            int p2 = 1;
            int p3 = 1;
            int p5 = 1;

            int i = 2;
            while (i <= n) {

                int res2 = dp[p2] * 2;
                int res3 = dp[p3] * 3;
                int res5 = dp[p5] * 5;

                dp[i] = Math.min(res2, Math.min(res3, res5));
                if (dp[i] == res2) {
                    p2++;
                }
                if (dp[i] == res3) {
                    p3++;
                }
                if (dp[i] == res5) {
                    p5++;
                }
                i++;
            }


            return dp[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}